package code401_500.code70_80;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。
 *
 * 连接词 定义为：一个完全由给定数组中的至少两个较短单词组成的字符串。
 *
 * 输入：words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
 * 输出：["catsdogcats","dogcatsdog","ratcatdogcat"]
 * 解释："catsdogcats" 由 "cats", "dog" 和 "cats" 组成;
 *      "dogcatsdog" 由 "dog", "cats" 和 "dog" 组成;
 *      "ratcatdogcat" 由 "rat", "cat", "dog" 和 "cat" 组成。
 *
 * 输入：words = ["cat","dog","catdog"]
 * 输出：["catdog"]
 */
public class _472findAllConcatenatedWordsInADict {

    Trie trie = new Trie();

    /**
     * 执行用时：     * 49 ms     * , 在所有 Java 提交中击败了    * 86.27%     * 的用户
     * 内存消耗：     * 47.7 MB     * , 在所有 Java 提交中击败了     * 54.90%     * 的用户
     * @param words
     * @return
     */
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        // lambda表达式进行排序
        Arrays.sort(words,(a,b)->a.length()-b.length());
        List<String> result = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            if(word.length()==0)continue;
            if(dfs(word,0)){
                result.add(word);
            }else {
                insert(word);
            }
        }
        return result;
    }

    public boolean dfs(String word,int start){
        if(word.length()==start)return true;
        Trie node = trie;
        for (int i = start; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            node = node.children[index];
            if(node == null) return false;
            if(node.isEnd){
                if(dfs(word,i+1))return true;
            }
        }
        return false;
    }

    public void insert(String word){
        Trie node = trie;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if(node.children[index] == null) node.children[index] = new Trie();
            node = node.children[index];
        }
        node.isEnd = true;
    }

}

class Trie{
    Trie[] children;
    boolean isEnd;

    public Trie(){
        children = new Trie[26];
        isEnd = false;
    }
}
